package com.zjsru.leetcode75.level1;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author: cookLee
 * @Date: 2023-12-03
 * 用最少数量的箭引爆气球
 */
public class FindMinArrowShots {
    /**
     * 主
     * \
     * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
     * 输出：2
     * 解释：气球可以用2支箭来爆破:
     * -在x = 6处射出箭，击破气球[2,8]和[1,6]。
     * -在x = 11处发射箭，击破气球[10,16]和[7,12]。
     * \
     * 输入：points = [[1,2],[3,4],[5,6],[7,8]]
     * 输出：4
     * 解释：每个气球需要射出一支箭，总共需要4支箭。
     * \
     * 输入：points = [[1,2],[2,3],[3,4],[4,5]]
     * 输出：2
     * 解释：气球可以用2支箭来爆破:
     * - 在x = 2处发射箭，击破气球[1,2]和[2,3]。
     * - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindMinArrowShots findMinArrowShots = new FindMinArrowShots();
        int[][] points = new int[][]{{10,16},{2,8},{1,6},{7,12}};
        System.out.println(findMinArrowShots.findMinArrowShots(points));
    }

    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        int ans = 1;
        int right = points[0][1];
        for (int i = 0; i < points.length; i++) {
            //此时需要第二支箭来射爆气球
            if (points[i][0] > right) {
                ans++;
                //同步更新新的最右侧边界值
                right = points[i][1];
            }
        }
        return ans;
    }

}
